package datastructure;

import java.util.ArrayList;
import java.util.Random;

/**
 * O(logn) for operation, tested on Poj3629
 * 
 * @author yinzichen
 * 
 * @param <T>
 */
public class SortedSkipList<T extends Comparable<T>> {
	class ListNode {
		T val;
		ListNode down;
		ListNode next;

		public ListNode(T val) {
			this.val = val;
		}
	}

	static final Random ran = new Random(0);
	static final double prob = 0.5;
	ListNode top;
	ListNode head;
	ListNode rear;
	int height;

	public SortedSkipList() {
		head = new ListNode(null);
		rear = new ListNode(null);
		head.next = rear;
		top = head;
		height = 1;
	}

	private int randomHeight() {
		int h = 0;
		double hasNext;
		do {
			h++;
			hasNext = ran.nextDouble();
		} while (hasNext < prob);
		return h;
	}

	private ArrayList<ListNode> find(T val, int k) {
		ArrayList<ListNode> level = new ArrayList<ListNode>();
		ListNode cur = top;
		int j = height;
		while (cur != null) {
			while (cur.next != rear && cur.next.val.compareTo(val) < 0) {
				cur = cur.next;
			}
			if (j <= k) {
				level.add(cur);
			}
			j--;
			cur = cur.down;
		}
		return level;
	}

	public void insert(T val) {
		int h = randomHeight();
		while (height < h) {
			ListNode newHead = new ListNode(null);
			newHead.next = rear;
			newHead.down = top;
			top = newHead;
			height++;
		}
		ArrayList<ListNode> level = find(val, h);
		ListNode down = null;
		for (int i = level.size() - 1; i >= 0; --i) {
			ListNode newNode = new ListNode(val);
			newNode.next = level.get(i).next;
			newNode.down = down;
			level.get(i).next = newNode;
			down = newNode;
		}
	}

	public T find(T val) {
		ArrayList<ListNode> level = find(val, 1);
		ListNode res = level.get(0).next;
		if (res != rear && val.compareTo(res.val) == 0)
			return res.val;
		return null;
	}

	public T delete(T val) {
		ArrayList<ListNode> level = find(val, height);
		ListNode res = level.get(level.size() - 1).next;
		if (res == rear || val.compareTo(res.val) != 0)
			return null;
		for (int i = level.size() - 1; i >= 0; --i) {
			if (level.get(i).next.val == res.val) {
				level.get(i).next = level.get(i).next.next;
			}
		}
		while (top.down != null && top.next == rear) {
			top = top.down;
			height--;
		}
		return res.val;
	}

	public static void main(String[] args) {
		SortedSkipList<Integer> a = new SortedSkipList<Integer>();
		for (int i = 0; i < 1000000; ++i) {
			a.insert(i);
		}
		for (int i = 0; i < 1000000; ++i) {
			a.delete(i);
		}
		a.insert(500000);
		for (int i = 0; i < 1000000; ++i) {
			if (a.find(i) != null)
				System.out.println(i);
		}
	}
}
